package linked_list;

import java.util.ArrayList;
import java.util.LinkedList;

public class 图书整理1 {
    class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
    //数组
    class Solution1 {
        public int[] reversePrint(ListNode head) {
            //计数就完事=-=
            ListNode cur = head;
            int count = 0;
            while (cur != null) {
                cur = cur.next;
                count++;
            }

            int[] arr = new int[count];

            cur = head;
            count--;
            while (cur != null && count >= 0) {
                arr[count--] = cur.val;
                cur = cur.next;
            }
            return arr;
        }
    }
    //递归
    class Solution2 {
        ArrayList<Integer> tmp = new ArrayList<Integer>();
        public int[] reverseBookList(ListNode head) {
            recur(head);
            int[] res = new int[tmp.size()];
            for(int i = 0; i < res.length; i++)
                res[i] = tmp.get(i);
            return res;
        }
        void recur(ListNode head) {
            if(head == null) return;
            recur(head.next);
            tmp.add(head.val);
        }
    }
    //辅助栈法
    class Solution3 {
        public int[] reverseBookList(ListNode head) {
            LinkedList<Integer> stack = new LinkedList<Integer>();
            while (head != null) {
                stack.addLast(head.val);
                head = head.next;
            }
            int[] res = new int[stack.size()];
            for (int i = 0; i < res.length; i++) {
                res[i] = stack.removeLast();
            }
            return res;
        }
    }
}